/**
* @description: 1014. 最佳观光组合
* @author hewei
* @date 2022/10/5 14:32
* @version 1.0
*/

public class MaxScoreSightseeingPair {

    public int maxScoreSightseeingPair(int[] values) {
        int n = values.length;
        int[] temp = new int[n];
        int max = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            max = Math.max(values[i] - i, max);
            temp[i] = max;
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            ans = Math.max(ans, values[i] + temp[i + 1] + i);
        }
        return ans;
    }
}
